@article{GallagerHS83,
  author    = {Robert G. Gallager and
               Pierre A. Humblet and
               Philip M. Spira},
  title     = {A Distributed Algorithm for Minimum-Weight Spanning Trees},
  journal   = {ACM Trans. Program. Lang. Syst.},
  volume    = {5},
  number    = {1},
  year      = {1983},
  pages     = {66-77},
  ee        = {http://doi.acm.org/10.1145/357195.357200},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{GoelKK10,
  author    = {Ashish Goel and
               Michael Kapralov and
               Sanjeev Khanna},
  title     = {Graph Sparsification via Refinement Sampling},
  journal   = {CoRR},
  volume    = {abs/1004.4915},
  year      = {2010},
  ee        = {http://arxiv.org/abs/1004.4915},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{GhaffariKuhn13,
  author    = {Mohsen Ghaffari and
               Fabian Kuhn},
  title     = {Distributed Minimum Cut Approximation},
  journal   = {CoRR},
  volume    = {abs/1305.5520},
  year      = {2013},
  ee        = {http://arxiv.org/abs/1305.5520},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{BravermanGPW13,
  author    = {Mark Braverman and
               Ankit Garg and
               Denis Pankratov and
               Omri Weinstein},
  title     = {From information to exact communication},
  booktitle = {STOC},
  year      = {2013},
  pages     = {151-160},
  ee        = {http://doi.acm.org/10.1145/2488608.2488628},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


article{KalyanasundaramS92,
  author    = {Bala Kalyanasundaram and
               Georg Schnitger},
  title     = {{The Probabilistic Communication Complexity of Set Intersection}},
  journal   = {SIAM J. Discrete Math.},
  volume    = {5},
  number    = {4},
  year      = {1992},
  pages     = {545-557},
  ee        = {http://dx.doi.org/10.1137/0405044},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

article{Razborov92,
  author    = {Alexander A. Razborov},
  title     = {{On the Distributional Complexity of Disjointness}},
  journal   = {Theor. Comput. Sci.},
  volume    = {106},
  number    = {2},
  year      = {1992},
  pages     = {385-390},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in ICALP'90}
}







@inproceedings{ChakrabartiCM08,
  author    = {Amit Chakrabarti and
               Graham Cormode and
               Andrew McGregor},
  title     = {Robust lower bounds for communication and stream computation},
  booktitle = {STOC},
  year      = {2008},
  pages     = {641-650},
  ee        = {http://doi.acm.org/10.1145/1374376.1374470},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
  crossref  = {DBLP:conf/stoc/2008},


@inproceedings{DasSarmaLNT12,
  author    = {Atish {Das Sarma} and
               Ashwin Lall and
               Danupon Nanongkai and
               Amitabh Trehan},
  title     = {Dense Subgraphs on Dynamic Networks},
  booktitle = {DISC},
  year      = {2012},
  pages     = {151-165},
  ee        = {http://dx.doi.org/10.1007/978-3-642-33651-5_11},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
  crossref  = {DBLP:conf/wdag/2012},

@inproceedings{Nanongkai13-ShortestPaths,
author    = {Danupon Nanongkai},
  title     = {Distributed approximation algorithms for weighted shortest
               paths},
  booktitle = {STOC},
  year      = {2014},
  pages     = {565-573},
  ee        = {http://doi.acm.org/10.1145/2591796.2591850},
  crossref  = {DBLP:conf/stoc/2014},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Newman91,
  author    = {Ilan Newman},
  title     = {Private vs. Common Random Bits in Communication Complexity},
  journal   = {Inf. Process. Lett.},
  volume    = {39},
  number    = {2},
  year      = {1991},
  pages     = {67-71},
  ee        = {http://dx.doi.org/10.1016/0020-0190(91)90157-D},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@book{KNbook,
 author = {E. Kushilevitz and N. Nisan},
 title = {{Communication complexity}},
 year = {1997},
 isbn = {0-521-56067-5},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
 }
 
@BOOK{MitzenmacherUpfalBook,
 author = "M. Mitzenmacher and E. Upfal",
 title = "Probability and Computing: Randomized Algorithms and Probabilistic Analysis",
 publisher = "Cambridge University Press",
 year = "2005"
}

@inproceedings{podc14,
  author    = {Michael Elkin and
               Hartmut Klauck and
               Danupon Nanongkai and
               Gopal Pandurangan},
  title     = {Can Quantum Communication Speed Up Distributed Computation?},
   booktitle = {PODC},
  year      = {2014},
}

@inproceedings{BabaiFS86,
  author    = {L. Babai and
               P. Frankl and
               J. Simon},
  title     = {{Complexity classes in communication complexity theory (preliminary
               version)}},
  booktitle = {FOCS},
  year      = {1986},
  pages     = {337-347},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{sicomp12,
  author    = {Atish Das Sarma and
               Stephan Holzer and
               Liah Kor and
               Amos Korman and
               Danupon Nanongkai and
               Gopal Pandurangan and
               David Peleg and
               Roger Wattenhofer},
  title     = {Distributed Verification and Hardness of Distributed Approximation},
  journal   = {SIAM J. Comput.},
  volume    = {41},
  number    = {5},
  year      = {2012},
  pages     = {1235-1265}
}

@inproceedings{podc11,
  author    = {Danupon Nanongkai and
               Atish Das Sarma and
               Gopal Pandurangan},
  title     = {A tight unconditional lower bound on distributed randomwalk
               computation},
  booktitle = {PODC},
  year      = {2011},
  pages     = {257-266}
}


article{BravermanGPW12,
  author    = {Mark Braverman and
               Ankit Garg and
               Denis Pankratov and
               Omri Weinstein},
  title     = {From Information to Exact Communication},
  journal   = {Electronic Colloquium on Computational Complexity (ECCC)},
  volume    = {19},
  year      = {2012},
  pages     = {171},
  ee        = {http://eccc.hpi-web.de/report/2012/171},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BravermanGPW12,
  author    = {Mark Braverman and
               Ankit Garg and
               Denis Pankratov and
               Omri Weinstein},
  title     = {From Information to Exact Communication},
  booktitle = {STOC},
  year      = {2013},
  ee        = {http://eccc.hpi-web.de/report/2012/171},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{ShiZ09,
 author = {Shi, Yaoyun and Zhu, Yufan},
 title = {Quantum communication complexity of block-composed functions},
 journal = {Quantum Info. Comput.},
 issue_date = {May 2009},
 volume = {9},
 number = {5},
 month = may,
 year = {2009},
 issn = {1533-7146},
 pages = {444--460},
 numpages = {17},
 url = {http://dl.acm.org/citation.cfm?id=2011791.2011798},
 acmid = {2011798},
 publisher = {Rinton Press, Incorporated},
 address = {Paramus, NJ},
 keywords = {communication complexity, polynomial approximation of Boolean functions, quantum information processing, quantum lower bound},
}

@article{luby,
 author = {Michael Luby},
 title = {A simple parallel algorithm for the maximal independent set problem},
 journal = {SIAM J. Comput.},
 volume = {15},
 number = {4},
 year = {1986},
 pages = {1036-1053}
}



@inproceedings{NanongkaiDP11,
  author    = {Danupon Nanongkai and
               Atish {Das Sarma} and
               Gopal Pandurangan},
  title     = {A tight unconditional lower bound on distributed randomwalk
               computation},
  booktitle = {PODC},
  year      = {2011},
  pages     = {257-266},
  ee        = {http://doi.acm.org/10.1145/1993806.1993853},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{graphcomm12,
  author    = {Gabor Ivanyos and  Hartmut Klauck and Troy Lee and Miklos Santha and Ronald de Wolf},
  title     = {New bounds on the classical and quantum
communication complexity of some graph
properties},
  journal = {Manuscript},
  year      = {2012}
}

@article{fooling12,
  author    = {Hartmut Klauck and Ronald de Wolf},
  title     = {Fooling One-Sided Quantum Protocols},
 journal = {Manuscript},
  year      = {2012}
}

@article{Bell64, title={On the einstein-podolsky-rosen paradox}, volume={1}, url={http://www.physics.princeton.edu/~mcdonald/examples/QM/bell_physics_1_195_64.pdf}, number={3}, journal={Physics}, publisher={Elsevier}, author={Bell, J S}, year={1964}, pages={195--200}}

@misc{giraph, 
  author={The Apache Project},
  title = {Apache {G}iraph},
  year = {http://giraph.apache.org/}
}

@misc{trinity,
  author={},
  title={Microsoft Trinity},
  year = {http://research.microsoft.com/trinity}
}

@misc{gps,
  author={},
  title= { GPS: A Graph Processing System},
  year = {http://infolab.stanford.edu/gps/}
}

@misc{trillion,
  author={Avery Ching},
  title = {Scaling Apache Giraph to a trillion edges},
  year = {2013, http://goo.gl/vKhloj},
}

@book{KayeLMBook06,
  author    = {Phillip Kaye and
               Raymond Laflamme and
               Michele Mosca},
  title     = {An Introduction to Quantum Computing},
  publisher = {Oxford University Press},
  year      = {2006},
  isbn      = {978-0-19-857000-4},
  pages     = {I-XI, 1-274},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{EPR35,
  added-at = {2007-11-11T14:56:13.000+0100},
  author = {Einstein, A. and Podolsky, B. and Rosen, N.},
  biburl = {http://www.bibsonomy.org/bibtex/27ebc89f882bf857e06159e705d6def1b/derkimbeimlesen},
  description = {Phys. Rev. 47 (1935): A. Einstein, B. Podolsky, and N. Rosen - Can Quantum-Mechanical Description of...},
  doi = {10.1103/PhysRev.47.777},
  interhash = {123f3f149d4e94566354a3587f9b600d},
  intrahash = {7ebc89f882bf857e06159e705d6def1b},
  journal = {Phys. Rev.},
  keywords = {TOREAD fundamental historical imported},
  month = May,
  number = 10,
  numpages = {3},
  pages = {777--780},
  publisher = {American Physical Society},
  timestamp = {2007-11-11T14:56:13.000+0100},
  title = {Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?},
  volume = 47,
  year = 1935
}

@article{Holevo73,
    author = {Holevo, A. S.},
    note = {English translation in {\it Problems of Information Transmission}, 9:177--183, 1973},
    journal = {Problemy Peredachi Informatsii},
    number = {3},
    pages = {3--11},
    priority = {2},
    title = {{Bounds for the quantity of information transmitted by a quantum communication channel}},
    volume = {9},
    year = {1973}
}

@inproceedings{Nayak99,
  author    = {Ashwin Nayak},
  title     = {Optimal Lower Bounds for Quantum Automata and Random Access
               Codes},
  booktitle = {FOCS},
  year      = {1999},
  pages     = {369-377},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/SFFCS.1999.814608},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{deWolf10,
  author    = {Ronald de Wolf},
  title     = {A note on quantum algorithms and the minimal degree of $\epsilon$-error
               polynomials for symmetric functions},
  journal   = {Quantum Information {\&} Computation},
  volume    = {8},
  number    = {10},
  year      = {2010},
  pages     = {943-950},
  ee        = {http://portal.acm.org/citation.cfm?id=2016989},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{Paturi92,
  author    = {Ramamohan Paturi},
  title     = {On the Degree of Polynomials that Approximate Symmetric
               Boolean Functions (Preliminary Version)},
  booktitle = {STOC},
  year      = {1992},
  pages     = {468-474},
  ee        = {http://doi.acm.org/10.1145/129712.129758},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@MISC{HorodeckiHH96,
  author = {Michal Horodecki and Pawel Horodecki and Ryszard Horodecki},
  title = {Separability of Mixed States: Necessary and Sufficient Conditions},
  url = {doi:10.1016/S0375-9601(96)00706-2},
  year = {1996}
}

@MASTERSTHESIS{Kremer95,
  AUTHOR =       {Ilan Kremer},
  TITLE =        {Quantum Communication},
  SCHOOL =       {The Hebrew University of Jerusalem},
  YEAR =         {1995}
}


@inproceedings{Yao93,
  author    = {Andrew Chi-Chih Yao},
  title     = {Quantum Circuit Complexity},
  booktitle = {FOCS},
  year      = {1993},
  pages     = {352-361},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/SFCS.1993.366852},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@book{Leighton91,
    author = {Leighton, Frank T.},
    edition = {1},
    howpublished = {Hardcover},
    isbn = {1558601171},
    keywords = {algorithms, architectures, available\_dei, reference, routing},
    posted-at = {2009-08-25 07:28:25},
    priority = {0},
    publisher = {Morgan Kaufmann Publishers},
    title = {{Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes}},
    year    = {1991}
}

@inproceedings{KuhnO11,
  author    = {Fabian Kuhn and
               Rotem Oshman},
  title     = {The Complexity of Data Aggregation in Directed Networks},
  booktitle = {DISC},
  year      = {2011},
  pages     = {416-431},
  ee        = {http://dx.doi.org/10.1007/978-3-642-24100-0_40},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{FrischknechtHW12,
  author    = {Silvio Frischknecht and
               Stephan Holzer and
               Roger Wattenhofer},
  title     = {Networks cannot compute their diameter in sublinear time},
  booktitle = {SODA},
  year      = {2012},
  pages     = {1150-1162},
  ee        = {http://portal.acm.org/citation.cfm?id=2095207{\&}CFID=63838676{\&}CFTOKEN=79617016},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{RazS95,
  author    = {Ran Raz and
               Boris Spieker},
  title     = {On the "Log Rank"-Conjecture in Communication Complexity},
  journal   = {Combinatorica},
  volume    = {15},
  number    = {4},
  year      = {1995},
  pages     = {567-588},
  ee        = {http://dx.doi.org/10.1007/BF01192528},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in FOCS'93}
}

@inproceedings{rohrig,
author = {H. Buhrman and H. Rohrig},
title = {Distributed quantum computing},
booktitle =  {Proceedings of Mathematical Foundations of Computer Science (MFCS), LNCS 2747},
year =  {2003},
pages = {1-20}
}


@ARTICLE{GaertnerBKCW08,
  author = {Sascha Gaertner and Mohamed Bourennane and Christian Kurtsiefer and Adan Cabello and Harald Weinfurter},
  title = {Experimental demonstration of a quantum protocol for Byzantine agreement   and liar detection},
  journal = {PHYS.REV.LETT.},
  volume = {100},
  pages = {070504},
  url = {doi:10.1103/PhysRevLett.100.070504},
  year = {2008}
}

@PHDTHESIS{DHont05,
  AUTHOR =       {Ellie D�Hondt},
  TITLE =        {Distributed quantum computation, A measurement-based approach},
  SCHOOL =       {Vrije Universiteit Brussel},
  YEAR =         {2005}
}


@inproceedings{Helm08,
	Author = {Louis K. Helm},
	Bibsource = {DBLP, http://dblp.uni-trier.de},
	Booktitle = {PODC},
	Date-Added = {2008-12-31 11:13:21 +0100},
	Date-Modified = {2008-12-31 11:13:21 +0100},
	Pages = {445},
	Title = {Brief announcement: Quantum distributed consensus},
	Year = {2008},
	Bdsk-Url-1 = {http://doi.acm.org/10.1145/1400751.1400841}
}

@MISC{PalKK03,
  author = {Sudebkumar Prasant Pal and Sudhir Kumar Singh and Somesh Kumar},
  title = {Multi-partite Quantum Entanglement versus Randomization: Fair and   Unbiased Leader Election in Networks},
  url = {http://www.citebase.org/abstract?id=oai:arXiv.org:quant-ph/0306195},
  year = {2003}
}

@article{KobayashiMT10,
  author    = {Hirotada Kobayashi and
               Keiji Matsumoto and
               Seiichiro Tani},
  title     = {Computing on Anonymous Quantum Network},
  journal   = {CoRR},
  volume    = {abs/1001.5307},
  year      = {2010},
  ee        = {http://arxiv.org/abs/1001.5307},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{KobayashiMT09,
  author    = {Hirotada Kobayashi and
               Keiji Matsumoto and
               Seiichiro Tani},
  title     = {Brief announcement: exactly electing a unique leader is
               not harder than computing symmetric functions on anonymous
               quantum networks},
  booktitle = {PODC},
  year      = {2009},
  pages     = {334-335},
  ee        = {http://doi.acm.org/10.1145/1582716.1582796},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{ChlebusKS10,
  author    = {Bogdan S. Chlebus and
               Dariusz R. Kowalski and
               Michal Strojnowski},
  title     = {Scalable Quantum Consensus for Crash Failures},
  booktitle = {DISC},
  year      = {2010},
  pages     = {236-250},
  ee        = {http://dx.doi.org/10.1007/978-3-642-15763-9_24},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{TaniKM05,
  author    = {Seiichiro Tani and
               Hirotada Kobayashi and
               Keiji Matsumoto},
  title     = {Exact Quantum Algorithms for the Leader Election Problem},
  booktitle = {STACS},
  year      = {2005},
  pages     = {581-592},
  ee        = {http://dx.doi.org/10.1007/978-3-540-31856-9_48},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

inproceedings{buhrman2,
  author    = {H. Buhrman and R. Cleve and A. Wigderson },
  title     = {Quantum verses Classical Communication and Computation},
  booktitle = {STOC},
  year      = {1998},
  pages     = {63-68}
}

@inproceedings{buhrman2,
  author    = {Harry Buhrman and
               Richard Cleve and
               Avi Wigderson},
  title     = {Quantum vs. Classical Communication and Computation},
  booktitle = {STOC},
  year      = {1998},
  pages     = {63-68},
  ee        = {http://doi.acm.org/10.1145/276698.276713},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Suomela09,
    author = {Jukka Suomela},
    title = {Survey of local algorithms},
    journal = {ACM Computing Surveys},
    year = {to appear}
}

@article{cleve,
  author    = {R. Cleve and H. Buhrman},
  title     = {Substituting Quantum Entanglement for Communication},
  journal   = {Physical Review A},
  volume    = {56(2)},
  year      = {1997},
  pages = {1201-1204}
}



@article{KuhnMW10,
  author    = {Fabian Kuhn and
               Thomas Moscibroda and
               Roger Wattenhofer},
  title     = {Local Computation: Lower and Upper Bounds},
  journal   = {CoRR},
  volume    = {abs/1011.5470},
  year      = {2010},
  ee        = {http://arxiv.org/abs/1011.5470},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{DenchevP08,
  author    = {Vasil S. Denchev and
               Gopal Pandurangan},
  title     = {Distributed quantum computing: a new frontier in distributed
               systems or science fiction?},
  journal   = {SIGACT News},
  volume    = {39},
  number    = {3},
  year      = {2008},
  pages     = {77-95},
  ee        = {http://doi.acm.org/10.1145/1412700.1412718},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{ben-or,
  author    = {M. Ben-Or and A. Hassidim},
  title     = {Fast Quantum Byzantine Agreement},
  booktitle   = {STOC},
  year      = {2005},
  pages     = {481-485}
}

@article{buhrman1,
  author    = {H. Buhrman and W. van Dam and P. Hoyer and A. Tapp },
  title     = {Quantum Multiparty Communication Complexity},
  journal   = {Physical Review A},
  volume    = {60},
  year      = {1999},
  pages     = {2737-2741}
}



@article{BroadbentT08,
  author    = {Anne Broadbent and
               Alain Tapp},
  title     = {Can quantum mechanics help distributed computing?},
  journal   = {SIGACT News},
  volume    = {39},
  number    = {3},
  year      = {2008},
  pages     = {67-76},
  ee        = {http://doi.acm.org/10.1145/1412700.1412717},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@ARTICLE{Tsirelson87,
  AUTHOR =       {Boris Tsirelson},
  TITLE =        {Quantum analogues of the Bell inequalities: the case of two spatially separated domains},
  JOURNAL =      {Journal of Soviet Mathematics},
  YEAR =         {1987},
  volume =       {36},
  pages =        {557--570}
}


@article{Shaltiel03,
  author    = {Ronen Shaltiel},
  title     = {Towards proving strong direct product theorems},
  journal   = {Computational Complexity},
  volume    = {12},
  number    = {1-2},
  year      = {2003},
  pages     = {1-22},
  ee        = {http://dx.doi.org/10.1007/s00037-003-0175-x},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{LeeZ10,
  author    = {Troy Lee and
               Shengyu Zhang},
  title     = {Composition Theorems in Communication Complexity},
  booktitle = {ICALP (1)},
  year      = {2010},
  pages     = {475-489},
  ee        = {http://dx.doi.org/10.1007/978-3-642-14165-2_41},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{LinialS09,
  author    = {Nati Linial and
               Adi Shraibman},
  title     = {Lower bounds in communication complexity based on factorization
               norms},
  journal   = {Random Struct. Algorithms},
  volume    = {34},
  number    = {3},
  year      = {2009},
  pages     = {368-394},
  ee        = {http://dx.doi.org/10.1002/rsa.20232},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in STOC'07}
}

@PHDTHESIS{BrietThesis11,
  AUTHOR =       {Jop Bri\"et},
  TITLE =        {Grothendieck Inequalities, Nonlocal Games and Optimization},
  SCHOOL =       {Universiteit van Amsterdam},
  YEAR =         {2011}
}




@article{LeeS09,
  author    = {Troy Lee and
               Adi Shraibman},
  title     = {Lower Bounds in Communication Complexity},
  journal   = {Foundations and Trends in Theoretical Computer Science},
  volume    = {3},
  number    = {4},
  year      = {2009},
  pages     = {263-398},
  ee        = {http://dx.doi.org/10.1561/0400000040},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{Watrous11,
  author    = {John Watrous},
  title     = {Guest column: an introduction to quantum information and
               quantum circuits 1},
  journal   = {SIGACT News},
  volume    = {42},
  number    = {2},
  year      = {2011},
  pages     = {52-67},
  ee        = {http://doi.acm.org/10.1145/1998037.1998053},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{GavoilleKM09,
  author    = {Cyril Gavoille and
               Adrian Kosowski and
               Marcin Markiewicz},
  title     = {What Can Be Observed Locally?},
  booktitle = {DISC},
  year      = {2009},
  pages     = {243-257},
  ee        = {http://dx.doi.org/10.1007/978-3-642-04355-0_26},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@book{AroraBarakBook09,
 author = {Arora, Sanjeev and Barak, Boaz},
 title = {Computational Complexity: A Modern Approach},
 year = {2009},
 isbn = {0521424267, 9780521424264},
 edition = {1st},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
}

@MASTERSTHESIS{RapaportThesis07,
  AUTHOR =       {Alex Rapaport},
  TITLE =        {Quantum Two Provers Interactive Proof Systems},
  SCHOOL =       {Tel Aviv University},
  YEAR =         {2007}
}


@article{BernsteinV97,
  author    = {Ethan Bernstein and
               Umesh V. Vazirani},
  title     = {Quantum Complexity Theory},
  journal   = {SIAM J. Comput.},
  volume    = {26},
  number    = {5},
  year      = {1997},
  pages     = {1411-1473},
  ee        = {http://dx.doi.org/10.1137/S0097539796300921},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in STOC'93}
}

@book{NielsenChuangBook,
    abstract = {{In this first comprehensive introduction to the main ideas and techniques  of quantum computation and information, Michael Nielsen and Isaac Chuang  ask the question: What are the ultimate physical limits to computation and communication? They detail such remarkable effects as fast quantum  algorithms, quantum teleportation, quantum cryptography and quantum error  correction. A wealth of accompanying figures and exercises illustrate and  develop the material in more depth. They describe what a quantum computer  is, how it can be used to solve problems faster than familiar "classical"  computers, and the real-world implementation of quantum computers. Their  book concludes with an explanation of how quantum states can be used to  perform remarkable feats of communication, and of how it is possible to  protect quantum states against the effects of noise.  }},
    author = {Nielsen, Michael A. and Chuang, Isaac L.},
    citeulike-article-id = {541803},
    citeulike-linkout-0 = {http://www.amazon.ca/exec/obidos/redirect?tag=citeulike09-20\&amp;path=ASIN/0521635039},
    citeulike-linkout-1 = {http://www.amazon.de/exec/obidos/redirect?tag=citeulike01-21\&amp;path=ASIN/0521635039},
    citeulike-linkout-2 = {http://www.amazon.fr/exec/obidos/redirect?tag=citeulike06-21\&amp;path=ASIN/0521635039},
    citeulike-linkout-3 = {http://www.amazon.jp/exec/obidos/ASIN/0521635039},
    citeulike-linkout-4 = {http://www.amazon.co.uk/exec/obidos/ASIN/0521635039/citeulike00-21},
    citeulike-linkout-5 = {http://www.amazon.com/exec/obidos/redirect?tag=citeulike07-20\&path=ASIN/0521635039},
    citeulike-linkout-6 = {http://www.worldcat.org/isbn/521635039},
    citeulike-linkout-7 = {http://books.google.com/books?vid=ISBN521635039},
    citeulike-linkout-8 = {http://www.amazon.com/gp/search?keywords=521635039\&index=books\&linkCode=qs},
    citeulike-linkout-9 = {http://www.librarything.com/isbn/521635039},
    day = {01},
    edition = {1},
    howpublished = {Paperback},
    isbn = {0521635039},
    month = jan,
    posted-at = {2007-09-03 10:03:03},
    priority = {5},
    publisher = {Cambridge University Press},
    title = {{Quantum Computation and Quantum Information (Cambridge Series on Information and the Natural Sciences)}},
    url = {http://www.amazon.com/exec/obidos/redirect?tag=citeulike07-20\&path=ASIN/0521635039},
    year = {2004}
}



@article{elkin-survey,
    author = "M. Elkin",
    title = "An Overview of Distributed Approximation",
    journal = {ACM SIGACT News Distributed Computing Column},
    year = {2004},
    month = {December},
    volume = {35},
    number = {4},
    pages = {40--57}
}

article{shma,
    author = {A. Ta-Shma},
    title = " Classical verses Quantum Communication Complexity",
    journal = {ACM SIGACT News},
    year = {1999},
    volume = {30},
    number = {3},
    pages = {25-34}
}

@article{shma,
  author    = {Amnon Ta-Shma},
  title     = {Classical versus quantum communication complexity},
  journal   = {SIGACT News},
  volume    = {30},
  number    = {3},
  year      = {1999},
  pages     = {25-34},
  ee        = {http://doi.acm.org/10.1145/333623.333628},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{khan-podc,
  author    = {Maleq Khan and
               Fabian Kuhn and
               Dahlia Malkhi and
               Gopal Pandurangan and
               Kunal Talwar},
  title     = {Efficient distributed approximation algorithms via probabilistic
               tree embeddings},
  booktitle = {PODC},
  year      = {2008},
  pages     = {263-272},
  ee        = {http://doi.acm.org/10.1145/1400751.1400787},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{PK09,
  author    = {Gopal Pandurangan and Maleq Khan},
  title     = {Theory of Communication Networks},
  booktitle = {Algorithms and Theory of Computation Handbook, Second Edition},
  year      = {2009},
  PUBLISHER =    {CRC Press},
}



@inproceedings{BuhrmanCWZ99,
  author    = {Harry Buhrman and
               Richard Cleve and
               Ronald de Wolf and
               Christof Zalka},
  title     = {Bounds for Small-Error and Zero-Error Quantum Algorithms},
  booktitle = {FOCS},
  year      = {1999},
  pages     = {358-368},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/SFFCS.1999.814607},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BlaisBM11,
  author    = {Eric Blais and
               Joshua Brody and
               Kevin Matulef},
  title     = {Property Testing Lower Bounds via Communication Complexity},
  booktitle = {IEEE Conference on Computational Complexity},
  year      = {2011},
  pages     = {210-220},
  ee        = {http://dx.doi.org/10.1109/CCC.2011.31},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{KlauckSW07,
  author    = {Hartmut Klauck and
               Robert Spalek and
               Ronald de Wolf},
  title     = {Quantum and Classical Strong Direct Product Theorems and
               Optimal Time-Space Tradeoffs},
  journal   = {SIAM J. Comput.},
  volume    = {36},
  number    = {5},
  year      = {2007},
  pages     = {1472-1493},
  ee        = {http://dx.doi.org/10.1137/05063235X},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in FOCS'04}
}

@article{KlauckSW07,
  author    = {Hartmut Klauck and
               Robert Spalek and
               Ronald de Wolf},
  title     = {Quantum and Classical Strong Direct Product Theorems and
               Optimal Time-Space Tradeoffs},
  journal   = {SIAM J. Comput.},
  volume    = {36},
  number    = {5},
  year      = {2007},
  pages     = {1472-1493},
  ee        = {http://dx.doi.org/10.1137/05063235X},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in FOCS'04}
}


@article{wolf1,
  author    = {
               Ronald de Wolf},
  title     = {Quantum Communication and Complexity},
  journal = {Theoretical Computer Science},
  year      = {2002},
  volume     = {287(1)},
 pages = {337-352}
}

@article{AaronsonA05,
  author    = {Scott Aaronson and
               Andris Ambainis},
  title     = {Quantum Search of Spatial Regions},
  journal   = {Theory of Computing},
  volume    = {1},
  number    = {1},
  year      = {2005},
  pages     = {47-79},
  ee        = {http://dx.doi.org/10.4086/toc.2005.v001a004},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in FOCS'03}
}

@article{Sherstov11,
  author    = {Alexander A. Sherstov},
  title     = {The Pattern Matrix Method},
  journal   = {SIAM J. Comput.},
  volume    = {40},
  number    = {6},
  year      = {2011},
  pages     = {1969-2000},
  ee        = {http://dx.doi.org/10.1137/080733644},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in STOC'08}
}

@inproceedings{Sherstov08,
  author    = {Alexander A. Sherstov},
  title     = {The pattern matrix method for lower bounds on quantum communication},
  booktitle = {STOC},
  year      = {2008},
  pages     = {85-94},
  ee        = {http://doi.acm.org/10.1145/1374376.1374392},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{raz,
  author    = {R. Raz},
  title     = {Exponential Separation of Quantum and Classical Communication Complexity},
  booktitle = {STOC},
  year      = {1999},
  pages     = {358-369}
}


@article{Razborov03,
  author={A A Razborov},
  title={Quantum communication complexity of symmetric predicates},
  journal={Izvestiya: Mathematics},
  volume={67},
  number={1},
  pages={145},
  url={http://stacks.iop.org/1064-5632/67/i=1/a=A08},
  year={2003},
  abstract={We completely (that is, up to a logarithmic factor) characterize the bounded-error quantum communication complexity of everypredicate ##IMG## [http://ej.iop.org/images/1064-5632/67/1/A08/tex_im_422_img1.gif] {$ f(x,y)$} ##IMG## [http://ej.iop.org/images/1064-5632/67/1/A08/tex_im_422_img2.gif] {$ x,y\subseteq \lbrack n \rbrack $} ) depending only on ##IMG## [http://ej.iop.org/images/1064-5632/67/1/A08/tex_im_422_img3.gif] {$ \vert x\cap y\vert$} . More precisely, givena predicate ##IMG## [http://ej.iop.org/images/1064-5632/67/1/A08/tex_im_422_img4.gif] {$ D$} on ##IMG## [http://ej.iop.org/images/1064-5632/67/1/A08/tex_im_422_img5.gif] {$ \{0,1,\dots,n\}$} , we put ----- -- ##IMG## [http://ej.iop.org/images/1064-5632/67/1/A08/tex_im_422_img6.gif] {$\displaystyle \ell_0(D)$} -- ##IMG## [http://ej.iop.org/images/1064-5632/67/1/A08/tex_im_422_img7.gif] {$\displaystyle \overset{\mathrm{def}}{=}\max\{\ell\mid 1\leqslant\ell\leqslant n/2\land D(\ell)\not\equiv D(\ell-1)\},$} --   ----- -- ##IMG## [http://ej.iop.org/images/1064-5632/67/1/A08/tex_im_422_img8.gif] {$\displaystyle \ell_1(D)$} -- ##IMG## [http://ej.iop.org/images/1064-5632/67/1/A08/tex_im_422_img9.gif] {$\displaystyle \overset{\mathrm{def}}{=}\max\{n-\ell\mid n/2\leqslant\ell<n\land D(\ell)\not\equiv D(\ell+1)\}.$} --   ----- Then the bounded-error quantum communication complexity of ##IMG## [http://ej.iop.org/images/1064-5632/67/1/A08/tex_im_422_img10.gif] {$ f_D(x,y)=D(\vert x\cap y\vert)$} is equal to ##IMG## [http://ej.iop.org/images/1064-5632/67/1/A08/tex_im_422_img11.gif] {$ \sqrt{n\ell_0(D)}+\ell_1(D)$} (up to a logarithmic factor). In particular, the complexity of the set disjointness predicate is equalto ##IMG## [http://ej.iop.org/images/1064-5632/67/1/A08/tex_im_422_img12.gif] {$ \Omega(\sqrt n\,)$} . This result holds both in the model with prior entanglement and in the model without it.}
}
	

@inproceedings{HajnalMT88,
  author    = {Andr{\'a}s Hajnal and
               Wolfgang Maass and
               Gy{\"o}rgy Tur{\'a}n},
  title     = {On the Communication Complexity of Graph Properties},
  booktitle = {STOC},
  year      = {1988},
  pages     = {186-191},
  ee        = {http://doi.acm.org/10.1145/62212.62228},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@article{DasSarmaHKKNPPW11,
  author    = {Atish {Das Sarma} and
               Stephan Holzer and
               Liah Kor and
               Amos Korman and
               Danupon Nanongkai and
               Gopal Pandurangan and
               David Peleg and
               Roger Wattenhofer},
  title     = {Distributed Verification and Hardness of Distributed Approximation},
  journal   = {SIAM J. Comput.},
  year    = {to appear},
  note      = {Available at http://arxiv.org/abs/1011.3049. Preliminary version appeared at STOC'11. }
}


inproceedings{DasSarmaHKKNPPW11,
  author    = {Atish {Das Sarma} and
               Stephan Holzer and
               Liah Kor and
               Amos Korman and
               Danupon Nanongkai and
               Gopal Pandurangan and
               David Peleg and
               Roger Wattenhofer},
  title     = {Distributed Verification and Hardness of Distributed Approximation},
  booktitle = {STOC},
  year      = {2011},
  pages     = {363-372},
  ee        = {http://doi.acm.org/10.1145/1993636.1993686},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Available at http://arxiv.org/abs/1011.3049.}
}

article{DHKKNPPW-ArXiv10,
  author    = {Atish {Das Sarma} and
               Stephan Holzer and
               Liah Kor and
               Amos Korman and
               Danupon Nanongkai and
               Gopal Pandurangan and
               David Peleg and
               Roger Wattenhofer},
  title     = {Distributed Verification and Hardness of Distributed Approximation},
  journal   = {CoRR},
  volume    = {abs/1011.3049},
  year      = {2010},
  ee        = {http://arxiv.org/abs/1011.3049},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BabaiFS86,
  author    = {L{\'a}szl{\'o} Babai and
               Peter Frankl and
               Janos Simon},
  title     = {{Complexity classes in communication complexity theory (preliminary
               version)}},
  booktitle = {FOCS},
  year      = {1986},
  pages     = {337-347},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Bar-YossefJKS04,
  author    = {Ziv Bar-Yossef and
               T. S. Jayram and
               Ravi Kumar and
               D. Sivakumar},
  title     = {{An information statistics approach to data stream and communication
               complexity}},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {68},
  number    = {4},
  year      = {2004},
  pages     = {702-732},
  ee        = {http://dx.doi.org/10.1016/j.jcss.2003.11.006},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in FOCS'02}
}

@article{Razborov92,
  author    = {Alexander A. Razborov},
  title     = {{On the Distributional Complexity of Disjointness}},
  journal   = {Theor. Comput. Sci.},
  volume    = {106},
  number    = {2},
  year      = {1992},
  pages     = {385-390},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in ICALP'90}
}

@article{KalyanasundaramS92,
  author    = {Bala Kalyanasundaram and
               Georg Schnitger},
  title     = {{The Probabilistic Communication Complexity of Set Intersection}},
  journal   = {SIAM J. Discrete Math.},
  volume    = {5},
  number    = {4},
  year      = {1992},
  pages     = {545-557},
  ee        = {http://dx.doi.org/10.1137/0405044},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note		= {Also in CCC'87}
}

@article{WuLBCRT99,
  author    = {Bang Ye Wu and
               Giuseppe Lancia and
               Vineet Bafna and
               Kun-Mao Chao and
               R. Ravi and
               Chuan Yi Tang},
  title     = {A Polynomial-Time Approximation Scheme for Minimum Routing
               Cost Spanning Trees},
  journal   = {SIAM J. Comput.},
  volume    = {29},
  number    = {3},
  year      = {1999},
  pages     = {761-778},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in SODA'98}
}

@book{peleg,
 author = {Peleg, David},
 title = {Distributed computing: a locality-sensitive approach},
 year = {2000},
 isbn = {0-89871-464-8},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }

@article{Luby86,
  author    = {Michael Luby},
  title     = {A Simple Parallel Algorithm for the Maximal Independent
               Set Problem},
  journal   = {SIAM J. Comput.},
  volume    = {15},
  number    = {4},
  year      = {1986},
  pages     = {1036-1053},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in STOC'85}
}

@article{Srinivasan,
  author    = {Alessandro Panconesi and
               Aravind Srinivasan},
  title     = {Randomized Distributed Edge Coloring via an Extension of
               the Chernoff-Hoeffding Bounds},
  journal   = {SIAM J. Comput.},
  volume    = {26},
  number    = {2},
  year      = {1997},
  pages     = {350-368},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'92}
}


@inproceedings{pemmaraju,
  author    = {Saurav Pandit and
               Sriram V. Pemmaraju},
  title     = {Return of the primal-dual: distributed metric facilitylocation},
  booktitle = {PODC},
  year      = {2009},
  pages     = {180-189},
  ee        = {http://doi.acm.org/10.1145/1582716.1582747},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{amos-kutten,
  author    = {Amos Korman and
               Shay Kutten},
  title     = {Distributed verification of minimum spanning trees},
  journal   = {Distributed Computing},
  volume    = {20},
  number    = {4},
  year      = {2007},
  pages     = {253-266},
  ee        = {http://dx.doi.org/10.1007/s00446-007-0025-1},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'06}
}
@article{linial,
  author    = {Nathan Linial},
  title     = {Locality in Distributed Graph Algorithms},
  journal   = {SIAM J. Comput.},
  volume    = {21},
  number    = {1},
  year      = {1992},
  pages     = {193-201},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@inproceedings{distcomb,
author = {F. Kuhn and R. Wattenhofer},
title = {Distributed Combinatorial Optimization},
booktitle ={Technical Report 426,
Dept. of Computer Science, ETH, Zurich},
year = {2004}
}

@inproceedings{bartal,
  author    = {Yair Bartal and
               John W. Byers and
               Danny Raz},
  title     = {{Global Optimization Using Local Information with Applications
               to Flow Control}},
  booktitle = {FOCS},
  year      = {1997},
  pages     = {303-312},
  ee        = {http://computer.org/proceedings/focs/8197/81970303abs.htm},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{czygrinow,
  author    = {Andrzej Czygrinow and
               Michal Hanckowiak and
               Edyta Szymanska},
  title     = {{Distributed algorithm for approximating the maximum matching}},
  journal   = {Discrete Applied Mathematics},
  volume    = {143},
  number    = {1-3},
  year      = {2004},
  pages     = {62-71},
  ee        = {http://dx.doi.org/10.1016/j.dam.2003.10.004},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{kuhn-podc03,
  author    = {Fabian Kuhn and
               Roger Wattenhofer},
  title     = {Constant-time distributed dominating set approximation},
  journal   = {Distributed Computing},
  volume    = {17},
  number    = {4},
  year      = {2005},
  pages     = {303-310},
  ee        = {http://dx.doi.org/10.1007/s00446-004-0112-5},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'03}
}

@article{dubhashi-dom,
  author    = {Devdatt P. Dubhashi and
               Alessandro Mei and
               Alessandro Panconesi and
               Jaikumar Radhakrishnan and
               Aravind Srinivasan},
  title     = {{Fast distributed algorithms for (weakly) connected dominating
               sets and linear-size skeletons}},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {71},
  number    = {4},
  year      = {2005},
  pages     = {467-479},
  ee        = {http://dx.doi.org/10.1016/j.jcss.2005.04.002},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in SODA'03}
}

@inproceedings{matching,
  author    = {Mirjam Wattenhofer and
               Roger Wattenhofer},
  title     = {Distributed Weighted Matching},
  booktitle = {DISC},
  year      = {2004},
  pages     = {335-348},
  ee        = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3274{\&}spage=335},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{Bar96,
  author    = {Yair Bartal},
  title     = {Probabilistic Approximations of Metric Spaces and Its Algorithmic
               Applications},
  booktitle = {FOCS},
  year      = {1996},
  pages     = {184-193},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@incollection{Dubhashi,
author = {Devdatt P. Dubhashi and Fabrizio Grandioni and Alessandro Panconesi},
title  = {{Distributed Algorithms via LP Duality and Randomization}},
booktitle  =  "Handbook of Approximation Algorithms and Metaheuristics",
publisher = "Chapman and Hall/CRC",
year =  2007
}

@inproceedings{Bar98,
  author    = {Yair Bartal},
  title     = {On Approximating Arbitrary Metrices by Tree Metrics},
  booktitle = {STOC},
  year      = {1998},
  pages     = {161-168},
  ee        = {http://doi.acm.org/10.1145/276698.276725},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{CCGGP98,
  author    = {Moses Charikar and
               Chandra Chekuri and
               Ashish Goel and
               Sudipto Guha and
               Serge A. Plotkin},
  title     = {Approximating a Finite Metric by a Small Number of Tree
               Metrics},
  booktitle = {FOCS},
  year      = {1998},
  pages     = {379-388},
  ee        = {http://computer.org/conferen/proceed/focs/9172/91720379abs.htm},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{CKR01-zero,
  author    = {Gruia C{\u{a}}linescu and
               Howard J. Karloff and
               Yuval Rabani},
  title     = {Approximation algorithms for the 0-extension problem},
  booktitle = {SODA},
  year      = {2001},
  pages     = {8-16},
  ee        = {http://doi.acm.org/10.1145/365411.365413},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{FHRT03,
  author    = {Jittat Fakcharoenphol and
               Chris Harrelson and
               Satish Rao and
               Kunal Talwar},
  title     = {An improved approximation algorithm for the 0-extension
               problem},
  booktitle = {SODA},
  year      = {2003},
  pages     = {257-265},
  ee        = {http://doi.acm.org/10.1145/644108.644153},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{khan-tcs,
  author    = {Maleq Khan and
               Gopal Pandurangan and
               V. S. Anil Kumar},
  title     = {A simple randomized scheme for constructing low-weight k-connected
               spanning subgraphs with applications to distributed algorithms},
  journal   = {Theor. Comput. Sci.},
  volume    = {385},
  number    = {1-3},
  year      = {2007},
  pages     = {101-114},
  ee        = {http://dx.doi.org/10.1016/j.tcs.2007.05.028},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{cocoon,
  author    = {Parinya Chalermsook and
               Jittat Fakcharoenphol},
  title     = {Simple Distributed Algorithms for Approximating Minimum
               Steiner Trees},
  booktitle = {COCOON},
  year      = {2005},
  pages     = {380-389},
  ee        = {http://dx.doi.org/10.1007/11533719_39},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{distLP,
  author    = {Christos H. Papadimitriou and
               Mihalis Yannakakis},
  title     = {Linear programming without the matrix},
  booktitle = {STOC},
  year      = {1993},
  pages     = {121-129},
  ee        = {http://doi.acm.org/10.1145/167088.167127},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@BOOK{Lynch,
 author = {Nancy Lynch},
 title = {Distributed Algorithms},
 publisher = {Morgan Kaufmann},
 year = {1996}
}

@book{ullman-book,
  author={Anand Rajaraman and Jeff Ullman},
    title={Mining of Massive Datasets},
    year={October 2011},
  publisher={Cambridge University Press}
}

@BOOK{vazirani,
 author = {V. Vazirani},
 title = {Approximation Algorithms},
 publisher = {Springer Verlag},
 year = {2004}
}

@book{lin-book,
  author={J. Lin and C. Dyer},
 title={ Data-Intensive Text Processing with MapReduce},
publisher={ Morgan Claypool Publishers},
 year={ 2010}
}


@article{KPK,
  author = {M. Khan and G. Pandurangan and V.S.A. Kumar},
  title = {Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks},
  journal = {IEEE Transactions on Parallel and Distributed Systems},
  year = "2008 (in press)",
  note = {available at http://staff.vbi.vt.edu/maleq/papers/TPDS.pdf}
}


@inproceedings{awerbuch-optimal,
    author = "B. Awerbuch",
    title = "Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems",
    booktitle = "19th  STOC",
    year = "1987",
}

@incollection{gopal-survey,
author = "G. Pandurangan and M. Khan",
title  = "Theory of Communication Networks",
booktitle = {Algorithms and Theory of Computation Handbook (second edition)},
editor =  "M.J. Atallah and M. Blanton",
publisher = "CRC Press (forthcoming)",
year = "2009",
note = {available at http://www.cs.purdue.edu/homes/gopal/tcn.pdf}
}


%16
@ARTICLE(DistMst:Gallager,
 author = "Gallager, R. and Humblet, P. and Spira, P.",
 title = "A Distributed Algorithm for Minimum-Weight Spanning Trees",
 journal = "ACM Trans. on Programming Languages and Systems",
 year = "1983",
 volume = "5",
 number = "1",
 pages = "66-77"
)

%17
@article{GarayKP93,
    author = "J. Garay and S. Kutten and D. Peleg",
    title = "A sublinear time distributed algorithm for minimum-weight spanning trees",
    journal = {SIAM J. on Computing},
    year = {1998},
    volume = {27},
    pages = {302--316},
    note  = {Also in FOCS'93}
}

@INPROCEEDINGS{Ravi,
  AUTHOR =       {B. Wu and G. Lancia and V. Bafna and K. Chao and R. Ravi and C. Tang},
  TITLE =        {A Polynomial Time Approximation Scheme for Minimum Routing Cost Spanning Trees},
  BOOKTITLE =    {9th SODA},
  YEAR =         {1998}
}


@INPROCEEDINGS{awerbuch,
  AUTHOR =       {B. Awerbuch},
  TITLE =        {Randomized Distributed Shortest Paths Algorithms},
  BOOKTITLE =    {21st STOC},
  YEAR =         {1989}
}


@article{cohen,
  author    = {Edith Cohen},
  title     = {{Size-Estimation Framework with Applications to Transitive
               Closure and Reachability}},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {55},
  number    = {3},
  year      = {1997},
  pages     = {441-453},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in FOCS'94}
}

@ARTICLE{cohen1,
  AUTHOR =       {E. Cohen and H. Kaplan},
  TITLE =        {Spatially-Decaying Aggregation Over a Network},
  JOURNAL =      {JCSS},
  YEAR =         {2007},
  volume =       {73},
  number =       {3},
  pages =        {265-288}
}

@ARTICLE{kunal,
  AUTHOR =       {J. Fakcharoenphol and S. Rao and K. Talwar},
  TITLE =        {A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics},
  JOURNAL =      {JCSS},
  YEAR =         {2004},
  volume =       {69},
  number =       {3},
  pages =        {485-497}
}

@article{elkin-faster,
  author    = {Michael Elkin},
  title     = {{A faster distributed protocol for constructing a minimum
               spanning tree}},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {72},
  number    = {8},
  year      = {2006},
  pages     = {1282-1308},
  ee        = {http://dx.doi.org/10.1016/j.jcss.2006.07.002},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in SODA'04}
}

@article{khan-disc,
  author    = {Maleq Khan and
               Gopal Pandurangan},
  title     = {{A fast distributed approximation algorithm for minimum spanning
               trees}},
  journal   = {Distributed Computing},
  volume    = {20},
  number    = {6},
  year      = {2008},
  pages     = {391-402},
  ee        = {http://dx.doi.org/10.1007/s00446-007-0047-8},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in DISC'06}
}



@inproceedings{peleg-bound,
    author = "D. Peleg and V. Rabinovich",
    title = "A near-tight lower bound on the time complexity of distributed MST construction",
    booktitle = "40th FOCS",
    year = "1999"
}

@BOOK(MU,
 author = "M. Mitzenmacher and E. Upfal",
 title = "Probability and Computing: Randomized Algorithms and Probabilistic Analysis",
 publisher = "Cambridge University Press",
 year = "2005"
)

@BOOK(Tel,
 author = {G. Tel},
 title = {Introduction to Distributed Algorithms},
 publisher = {Cambridge University Press},
 year = {1994}
)

@ARTICLE{peleg1,
  AUTHOR =       {D. Peleg},
  TITLE =        {A Time Optimal Leader Election algorithm in General Networks},
  JOURNAL =      {J. Parallel and Distributed Computing},
  YEAR =         {1990},
  volume =       {8},
  pages=       {96-99}
}

% Distributed Approximation

@InProceedings{kuhn-soda06,
  author =   {F. Kuhn and T. Moscibroda and R. Wattenhofer},
  title =    {{The Price of Being Near-Sighted}},
  booktitle =  {17th  SODA},
  year =     {2006}
}

@inproceedings{kuhn-podc04,
  author    = {Fabian Kuhn and
               Thomas Moscibroda and
               Roger Wattenhofer},
  title     = {What cannot be computed locally!},
  booktitle = {PODC},
  year      = {2004},
  pages     = {300-309},
  ee        = {http://doi.acm.org/10.1145/1011767.1011811},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@InProceedings{kuhn-spaa07,
  author    = {F. Kuhn and T. Moscibroda},
  title     = {{Distributed Approximation of Capacitated Dominating Sets}},
  booktitle = {19th SPAA},
  year      = {2007}
}

@article{jia02,
  author    = {Lujun Jia and
               Rajmohan Rajaraman and
               Torsten Suel},
  title     = {{An efficient distributed algorithm for constructing small
               dominating sets}},
  journal   = {Distributed Computing},
  volume    = {15},
  number    = {4},
  year      = {2002},
  pages     = {193-205},
  ee        = {http://link.springer.de/link/service/journals/00446/bibs/2015004/20150193.htm},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@InProceedings{grandoni05,
  author =       {F. Grandoni and J. K\"onemann and A. Panconesi and M. Sozio},
  title =        {Primal-Dual Based Distributed Algorithms for Vertex Cover
                  with Semi-Hard Capacities},
  booktitle =    "24th  PODC",
  year =         2005
}


@inproceedings{KhanKMPT08,
  author    = {Maleq Khan and
               Fabian Kuhn and
               Dahlia Malkhi and
               Gopal Pandurangan and
               Kunal Talwar},
  title     = {Efficient distributed approximation algorithms via probabilistic
               tree embeddings},
  booktitle = {PODC},
  year      = {2008},
  pages     = {263-272},
  ee        = {http://doi.acm.org/10.1145/1400751.1400787},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Elkin-sigact04,
  author    = {Michael Elkin},
  title     = {{Distributed approximation: a survey}},
  journal   = {SIGACT News},
  volume    = {35},
  number    = {4},
  year      = {2004},
  pages     = {40-57},
  ee        = {http://doi.acm.org/10.1145/1054916.1054931},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{KuttenP98,
  author    = {Shay Kutten and
               David Peleg},
  title     = {{Fast Distributed Construction of Small $k$-Dominating
               Sets and Applications}},
  journal   = {J. Algorithms},
  volume    = {28},
  number    = {1},
  year      = {1998},
  pages     = {40-66},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'95}
}

@article{Thurimella97,
  author    = {Ramakrishna Thurimella},
  title     = {{Sub-Linear Distributed Algorithms for Sparse Certificates
               and Biconnected Components}},
  journal   = {J. Algorithms},
  volume    = {23},
  number    = {1},
  year      = {1997},
  pages     = {160-179},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'95}
}


@article{LotkerPP06,
  author    = {Zvi Lotker and
               Boaz Patt-Shamir and
               David Peleg},
  title     = {{Distributed MST for constant diameter graphs}},
  journal   = {Distributed Computing},
  volume    = {18},
  number    = {6},
  year      = {2006},
  pages     = {453-460},
  ee        = {http://dx.doi.org/10.1007/s00446-005-0127-6},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'01}
}


@inproceedings{LotkerPPP03,
  author    = {Zvi Lotker and
               Elan Pavlov and
               Boaz Patt-Shamir and
               David Peleg},
  title     = {{MST construction in $O(\log \log n)$ communication rounds}},
  booktitle = {SPAA},
  year      = {2003},
  pages     = {94-100},
  ee        = {http://doi.acm.org/10.1145/777412.777428},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Elkin05,
  author    = {Michael Elkin},
  title     = {{Computing almost shortest paths}},
  journal   = {ACM Transactions on Algorithms},
  volume    = {1},
  number    = {2},
  year      = {2005},
  pages     = {283-323},
  ee        = {http://doi.acm.org/10.1145/1103963.1103968},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'01}
}


@article{Elkin06,
  author    = {Michael Elkin},
  title     = {{An Unconditional Lower Bound on the Time-Approximation Trade-off
               for the Distributed Minimum Spanning Tree Problem}},
  journal   = {SIAM J. Comput.},
  volume    = {36},
  number    = {2},
  year      = {2006},
  pages     = {433-456},
  ee        = {http://dx.doi.org/10.1137/S0097539704441058},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in STOC'04}
}


article{KorKP10,
  author    = {Liah Kor and Amos Korman and David Peleg},
  title     = {{Tight bounds for distributed MST verification}},
  journal   = {STACS},
  year      = {2011}
}

@inproceedings{KorKP11,
  author    = {Liah Kor and
               Amos Korman and
               David Peleg},
  title     = {Tight Bounds For Distributed MST Verification},
  booktitle = {STACS},
  year      = {2011},
  pages     = {69-80},
  ee        = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.69},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@book{KNbook,
 author = {Eyal Kushilevitz and Noam Nisan},
 title = {{Communication complexity}},
 year = {1997},
 isbn = {0-521-56067-5},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
 }

@article{setdisj-survey,
 author = {Chattopadhyay, Arkadev and Pitassi, Toniann},
 title = {{The Story of Set Disjointness}},
 journal = {SIGACT News},
 volume = {41},
 number = {3},
 year = {2010},
 issn = {0163-5700},
 pages = {59--85},
 doi = {http://doi.acm.org/10.1145/1855118.1855133},
 publisher = {ACM},
 address = {New York, NY, USA},
 }

@article{tarjan,
  author    = {Robert Endre Tarjan},
  title     = {Applications of Path Compression on Balanced Trees},
  journal   = {J. ACM},
  volume    = {26},
  number    = {4},
  year      = {1979},
  pages     = {690-715},
  ee        = {http://doi.acm.org/10.1145/322154.322161},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{peleg-mst,
  author    = {Juan A. Garay and
               Shay Kutten and
               David Peleg},
  title     = {{A Sublinear Time Distributed Algorithm for Minimum-Weight
               Spanning Trees}},
  journal   = {SIAM J. Comput.},
  volume    = {27},
  number    = {1},
  year      = {1998},
  pages     = {302-316},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in FOCS '93}
}


@article{PelegR00,
  author    = {David Peleg and
               Vitaly Rubinovich},
  title     = {{A Near-Tight Lower Bound on the Time Complexity of Distributed
               Minimum-Weight Spanning Tree Construction}},
  journal   = {SIAM J. Comput.},
  volume    = {30},
  number    = {5},
  year      = {2000},
  pages     = {1427-1442},
  ee        = {http://epubs.siam.org/sam-bin/dbq/article/36974},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in FOCS'99}
}

@MISC{TCSStack10,
    TITLE = {{Lower Bound of Checking Graph Connectivity on Stream}},
    AUTHOR = {Srikanth (http://cstheory.stackexchange.com/users/227/srikanth)},
    HOWPUBLISHED = {http://cstheory.stackexchange.com},
    NOTE = {URL (accessed 2010-09-29): http://cstheory.stackexchange.com/questions/1763},
    EPRINT = {http://cstheory.stackexchange.com/questions/1763},
    URL = {http://cstheory.stackexchange.com/questions/1763},
}

@inproceedings{Yao77,
  author    = {Andrew Chi-Chih Yao},
  title     = {{Probabilistic Computations: Toward a Unified Measure of
               Complexity}},
  booktitle = {FOCS},
  year      = {1977},
  pages     = {222-227},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@book{Vazirani-book,
    author = {Vazirani, Vijay V.},
    howpublished = {Hardcover},
    isbn = {3540653678},
    keywords = {algorithms},
    month = {July},
    publisher = {Springer},
    title = {Approximation Algorithms},
    year = {2001}
}


@incollection{HenzingerRR98,
 author = {Henzinger, Monika R. and Raghavan, Prabhakar and Rajagopalan, Sridhar},
 title = {Computing on data streams},
 booktitle = {External memory algorithms},
 editor = {Abello, James M. and Vitter, Jeffrey Scott},
 year = {1999},
 isbn = {0-8218-1184-3},
 pages = {107--118},
 numpages = {12},
 url = {http://portal.acm.org/citation.cfm?id=327766.327782},
 acmid = {327782},
 publisher = {American Mathematical Society},
 address = {Boston, MA, USA},
}

@inproceedings{DBLP:conf/wdag/DolevLP12,
  author    = {Danny Dolev and
               Christoph Lenzen and
               Shir Peled},
  title     = {"Tri, Tri Again": Finding Triangles and Small Subgraphs
               in a Distributed Setting - (Extended Abstract)},
  booktitle = {DISC},
  year      = {2012},
  pages     = {195-209},
  ee        = {http://dx.doi.org/10.1007/978-3-642-33651-5_14},
  crossref  = {DBLP:conf/wdag/2012},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}




@inproceedings{DBLP:conf/podc/SarmaNP09,
  author    = {Atish {Das Sarma} and
               Danupon Nanongkai and
               Gopal Pandurangan},
  title     = {Fast distributed random walks},
  booktitle = {PODC},
  year      = {2009},
  pages     = {161-170},
  ee        = {http://doi.acm.org/10.1145/1582716.1582745},
  crossref  = {DBLP:conf/podc/2009},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{DBLP:conf/icdcn/SarmaMPU13,
  author    = {Atish {Das Sarma} and
               Anisur Rahaman Molla and
               Gopal Pandurangan and
               Eli Upfal},
  title     = {Fast Distributed PageRank Computation},
  booktitle = {ICDCN},
  year      = {2013},
  pages     = {11-26},
  ee        = {http://dx.doi.org/10.1007/978-3-642-35668-1_2},
  crossref  = {DBLP:conf/icdcn/2013},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{baswana,
  author    = {Surender Baswana and
               Sandeep Sen},
  title     = {A simple and linear time randomized algorithm for computing
               sparse spanners in weighted graphs},
  journal   = {Random Struct. Algorithms},
  volume    = {30},
  number    = {4},
  year      = {2007},
  pages     = {532-563},
  ee        = {http://dx.doi.org/10.1002/rsa.20130},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/osdi/DeanG04,
  author    = {Jeffrey Dean and
               Sanjay Ghemawat},
  title     = {MapReduce: Simplified Data Processing on Large Clusters},
  booktitle = {OSDI},
  year      = {2004},
  pages     = {137-150},
  ee        = {http://www.usenix.org/events/osdi04/tech/dean.html},
  crossref  = {DBLP:conf/osdi/2004},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{pregel,
  author    = {Grzegorz Malewicz and
               Matthew H. Austern and
               Aart J. C. Bik and
               James C. Dehnert and
               Ilan Horn and
               Naty Leiser and
               Grzegorz Czajkowski},
  title     = {Pregel: a system for large-scale graph processing},
  booktitle = {SIGMOD Conference},
  year      = {2010},
  pages     = {135-146},
  ee        = {http://doi.acm.org/10.1145/1807167.1807184},
  crossref  = {DBLP:conf/sigmod/2010},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{graphlab,
  author    = {Yucheng Low and
               Joseph Gonzalez and
               Aapo Kyrola and
               Danny Bickson and
               Carlos Guestrin and
               Joseph M. Hellerstein},
  title     = {GraphLab: A New Framework For Parallel Machine Learning},
  booktitle = {UAI},
  year      = {2010},
  pages     = {340-349},
  ee        = {http://uai.sis.pitt.edu/displayArticleDetails.jsp?mmnu=1{\&}smnu=2{\&}article_id=2126{\&}proceeding_id=26},
  crossref  = {DBLP:conf/uai/2010},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{chakrabarti,
  author    = {Amit Chakrabarti and
               Graham Cormode and
               Andrew McGregor},
  title     = {Robust Lower Bounds for Communication and Stream Computation},
  journal   = {Electronic Colloquium on Computational Complexity (ECCC)},
  volume    = {18},
  year      = {2011},
  pages     = {62},
  ee        = {http://eccc.hpi-web.de/report/2011/062},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{filtering-spaa,
  author    = {Silvio Lattanzi and
               Benjamin Moseley and
               Siddharth Suri and
               Sergei Vassilvitskii},
  title     = {Filtering: a method for solving graph problems in MapReduce},
  booktitle = {SPAA},
  year      = {2011},
  pages     = {85-94},
  ee        = {http://doi.acm.org/10.1145/1989493.1989505},
  crossref  = {DBLP:conf/spaa/2011},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{soda-mapreduce,
  author    = {Howard J. Karloff and
               Siddharth Suri and
               Sergei Vassilvitskii},
  title     = {A Model of Computation for MapReduce},
  booktitle = {SODA},
  year      = {2010},
  pages     = {938-948},
  ee        = {http://www.siam.org/proceedings/soda/2010/SODA10_076_karloffh.pdf},
  crossref  = {DBLP:conf/soda/2010},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{stanton,
  author    = {Isabelle Stanton and
               Gabriel Kliot},
  title     = {Streaming graph partitioning for large distributed graphs},
  booktitle = {KDD},
  year      = {2012},
  pages     = {1222-1230},
  ee        = {http://doi.acm.org/10.1145/2339530.2339722},
  crossref  = {DBLP:conf/kdd/2012},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{cloud,
  author    = {Nikhil Bansal and
               Kang-Won Lee and
               Viswanath Nagarajan and
               Murtaza Zafer},
  title     = {Minimum congestion mapping in a cloud},
  booktitle = {PODC},
  year      = {2011},
  pages     = {267-276},
  ee        = {http://doi.acm.org/10.1145/1993806.1993854},
  crossref  = {DBLP:conf/podc/2011},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{1212.1121v1,
  author    = {Isabelle Stanton},
  title     = {Streaming Balanced Graph Partitioning for Random Graphs},
  journal   = {CoRR},
  volume    = {abs/1212.1121},
  year      = {2012},
  ee        = {http://arxiv.org/abs/1212.1121},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{lin-paper,
 author = {Lin, Jimmy and Schatz, Michael},
 title = {Design patterns for efficient graph algorithms in MapReduce},
 booktitle = {Proceedings of the Eighth Workshop on Mining and Learning with Graphs},
 series = {MLG '10},
 year = {2010},
 isbn = {978-1-4503-0214-2},
 location = {Washington, D.C.},
 pages = {78--85},
 numpages = {8},
 url = {http://doi.acm.org/10.1145/1830252.1830263},
 doi = {10.1145/1830252.1830263},
 acmid = {1830263},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@inproceedings{woodruff,
  author    = {David P. Woodruff and
               Qin Zhang},
  title     = {When Distributed Computation Is Communication Expensive},
  booktitle = {DISC},
  year      = {2013},
  pages     = {16-30},
  ee        = {http://dx.doi.org/10.1007/978-3-642-41527-2_2},
  crossref  = {DBLP:conf/wdag/2013},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{beyond-hadoop-cacm,
  added-at = {2013-01-21T00:00:00.000+0100},
  author = {Mone, Gregory},
  journal = {Commun. ACM},
  keywords = {dblp},
  number = 1,
  pages = {22-24},
  title = {Beyond Hadoop.},
  volume = 56,
  year = 2013
}

@book{panconesi,
  author={Dubhashi and Panconesi},
title ={Concentration of Measure for Analysis of Randomized Algorithms},
publisher = {Cambridge University Press},
year={2012}
}

@inproceedings{lenzen-routing,
  author    = {Christoph Lenzen},
  title     = {Optimal deterministic routing and sorting on the congested
               clique},
  booktitle = {PODC},
  year      = {2013},
  pages     = {42-50},
  ee        = {http://doi.acm.org/10.1145/2484239.2501983},
  crossref  = {DBLP:conf/podc/2013},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@inproceedings{icdcn13,
  author    = {Shay Kutten and
               Gopal Pandurangan and
               David Peleg and
               Peter Robinson and
               Amitabh Trehan},
  title     = {Sublinear Bounds for Randomized Leader Election},
  booktitle = {ICDCN},
  year      = {2013},
  pages     = {348-362},
  ee        = {http://dx.doi.org/10.1007/978-3-642-35668-1_24},
  crossref  = {DBLP:conf/icdcn/2013},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{kelsen,
  author    = {Pierre Kelsen},
  title     = {On the Parallel Complexity of Computing a Maximal Independent
               Set in a Hypergraph},
  booktitle = {STOC},
  year      = {1992},
  pages     = {339-350},
  ee        = {http://doi.acm.org/10.1145/129712.129745},
  crossref  = {DBLP:conf/stoc/STOC24},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{beame,
  author    = {Paul Beame and
               Michael Luby},
  title     = {Parallel Search for Maximal Independence Given Minimal Dependence},
  booktitle = {SODA},
  year      = {1990},
  pages     = {212-218},
  ee        = {http://dl.acm.org/citation.cfm?id=320176.320200},
  crossref  = {DBLP:conf/soda/1990},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@inproceedings{taskalloc,
  author    = {Andrew Drucker and
               Fabian Kuhn and
               Rotem Oshman},
  title     = {The communication complexity of distributed task allocation},
  booktitle = {PODC},
  year      = {2012},
  pages     = {67-76},
  ee        = {http://doi.acm.org/10.1145/2332432.2332443},
  crossref  = {DBLP:conf/podc/2012},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{densest,
  author    = {Atish Das Sarma and
               Ashwin Lall and
               Danupon Nanongkai and
               Amitabh Trehan},
  title     = {Dense Subgraphs on Dynamic Networks},
  booktitle = {Distributed Computing - 26th International Symposium, {DISC} 2012,
               Salvador, Brazil, October 16-18, 2012. Proceedings},
  year      = {2012},
  pages     = {151--165},
  crossref  = {DBLP:conf/wdag/2012},
  url       = {http://dx.doi.org/10.1007/978-3-642-33651-5_11},
  doi       = {10.1007/978-3-642-33651-5_11},
  timestamp = {Sun, 05 Oct 2014 09:20:44 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/wdag/SarmaLNT12},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}
